package com.leetCode.ArrayDemo;

import java.util.*;

public class arrayMergeDemo {
    public static void main(String[] args) {
        int[][] param = new int[5][2];
        param[0] = new int[]{1,3};
        param[1] = new int[]{2,6};
        param[2] = new int[]{6,7};
        param[3] = new int[]{8,10};
        param[4] = new int[]{15,18};
        System.out.println(merge2(param));
    }

    /**
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
     * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
     *
     * 示例 1：
     *
     * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出：[[1,6],[8,10],[15,18]]
     * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     * 示例 2：
     *
     * 输入：intervals = [[1,4],[4,5]]
     * 输出：[[1,5]]
     * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
     * 提示：
     *
     * 1 <= intervals.length <= 104
     * intervals[i].length == 2
     * 0 <= starti <= endi <= 104
     * Related Topics
     * 数组
     * 排序
     */
    public static int[][] merge(int[][] intervals){
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
    public static int[][] merge1(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        List<Integer> skipArr = new ArrayList<>();
        List<String> remRepArr = new ArrayList<>();
        for (int i = 0;i < intervals.length;i++){
            if (!skipArr.contains(i)){
                int[] one = intervals[i];
                int oneL = one[0];
                int oneR = one[one.length - 1];
                for (int j = i + 1;j < intervals.length;j++){
                    int[] two = intervals[j];
                    int twoL = two[0];
                    int twoR = two[two.length - 1];
                    if (oneL >= twoL){
                        if (oneL <= twoR){
                            if (oneR > twoR){
                                oneL = twoL;
                                skipArr.add(j);
                            } else {
                                oneL = twoL;
                                oneR = twoR;
                                skipArr.add(j);
                            }
                        }
                    } else {
                        if (oneR >= twoL){
                            if (oneR < twoR){
                                oneR = twoR;
                            }
                            skipArr.add(j);
                        }
                    }
                }
                one[0] = oneL;
                one[1] = oneR;
                String remRepStr = "" + oneL + oneR;
                if (!remRepArr.contains(remRepStr)){
                    res.add(one);
                }
                remRepArr.add(remRepStr);
            }
        }
        int[][] array = new int[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            array[i] = res.get(i);
            System.out.println("左区间：" + res.get(i)[0] + "右区间：" + res.get(i)[1]);
        }
        return array;
    }

    /**
     * 对二维数组进行排序即可
     */
    public static int[][] merge2(int[][] intervals) {
        if (intervals.length == 0){
            return new int[0][2];
        }
        Arrays.sort(intervals, (a, b) -> {
            return Integer.compare(a[0], b[0]);
        });
        List<int[]> merged = new ArrayList<>();
        for (int i = 0;i < intervals.length;++i){
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L){
                merged.add(new int[]{L,R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1],R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}
